#include <iostream> 
using namespace std;

void swap(int &a, int &b)
{
	int t = a;
	a = b;
	b = t;
}

void printArr(int *arrP,int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d ",*arrP++);
    printf("\n");
}

int main()
{
	int arr[]={6,5,4,9,2,1,3,9,4,2,5,7,8};
	int l = sizeof(arr)/sizeof(int);
	int step = l;
	while(step>1)
	{
		step/=2;
		cout<<"----------step = "<<step<<"------------"<<endl;
		for(int i = step;i<l;i+=step)
		{
            int j = i;
            int cur = arr[j];
            while (j-step>=0 && cur<arr[j-step])
            {
//                printf("compare %d and %d \n",arr[j],arr[j-step]);
                arr[j]=arr[j-step];
                j-=step;
            }
            arr[j]=cur;
//            printf("i:%d, j:%d, cur:%d ",i,j,cur);
//            printArr(arr,l);
		}
//		cout<<endl;
	}
	printArr(arr,l);
}
